package com.wkh.datastructure.deque;

import java.lang.invoke.VarHandle;
import java.util.Iterator;

//基于双向环形链表实现双端队列
public class LinkedListDeque<E> implements Deque<E>,Iterable<E> {
    static class Node<E>{
        Node<E> prev;
        E value;
        Node<E> next;

        public Node(Node<E> prev, E value, Node<E> next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    //容量
    private int capacity;
    //元素个数
    private int size;
    //哨兵
    private Node<E> sentinel = new Node<>(null,null,null);

    public LinkedListDeque(int capacity) {
        this.capacity = capacity;
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

    /**
     * 从队头添加
     *
     * @param value
     */
    @Override
    public boolean offerFirst(E value) {
        if (isFull()){
            return false;
        }
        Node<E> newNode = new Node<>(sentinel, value, sentinel.next);
        sentinel.next.prev = newNode;
        sentinel.next = newNode;
        size++;
        return true;
    }

    /**
     * 从队尾添加
     *
     * @param value
     * @return
     */
    @Override
    public boolean offerLast(E value) {
        if (isFull()){
            return false;
        }
        Node<E> newNode = new Node<>(sentinel.prev, value, sentinel);
        sentinel.prev.next = newNode;
        sentinel.prev = newNode;
        size++;
        return true;
    }

    /**
     * 从队头删除
     *
     * @return
     */
    @Override
    public E poolFirst() {
        if (isEmpty()){
            return null;
        }
        Node<E> removed = sentinel.next;
        Node<E> a = this.sentinel;
        Node<E> b = removed.next;
        a.next = b;
        b.prev = a;
        return removed.value;
    }

    /**
     * 从队尾删除
     *
     * @return
     */
    @Override
    public E poolLast() {
        if (isEmpty()){
            return null;
        }
        Node<E> removed = sentinel.prev;
        Node<E> a = this.sentinel;
        Node<E> b = removed.prev;
        a.prev = b;
        b.next = a;
        return removed.value;
    }

    /**
     * 查看队头元素
     *
     * @return
     */
    @Override
    public E peekFirst() {
        if (isEmpty()){
            return null;
        }
        E value = sentinel.next.value;
        return value;
    }

    /**
     * 查看队尾元素
     *
     * @return
     */
    @Override
    public E peekLast() {
        if (isEmpty()){
            return null;
        }
        E value = sentinel.prev.value;
        return value;
    }

    /**
     * 判断是否为空
     *
     * @return
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 判断是否已满
     *
     * @return
     */
    @Override
    public boolean isFull() {
        return size == capacity;
    }

    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = sentinel.next;
            @Override
            public boolean hasNext() {
                return p!=sentinel;
            }

            @Override
            public E next() {
                E value = p.value;
                 p = p.next;
                return value;
            }
        };
    }
}
